/*
 * @lc app=leetcode.cn id=1011 lang=golang
 *
 * [1011] 在 D 天内送达包裹的能力
 */
package Solutions

import "sort"

// @lc code=start
func shipWithinDays(weights []int, days int) int {
	maxWeight := -1
	sum := 0
	for _, v := range weights {
		if maxWeight < v {
			maxWeight = v
		}
		sum += v
	}
	var f = func(k int) bool {
		day := 1
		t := k
		for i := 0; i < len(weights); i++ {
			if t >= weights[i] {
				t -= weights[i]
			} else {
				day++
				t = k
				i--
				if day > days {
					return false
				}
			}
		}
		return true
	}
	return sort.Search(sum-maxWeight, func(i int) bool {
		return f(maxWeight + i)
	}) + maxWeight
}

// @lc code=end
